package leetcode_ago.bin_tree;

/**
 * 给你一棵二叉搜索树(BST)的root，请你按中序遍历将其重新排列为一棵递增顺序搜索树
 * 使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 * 树中节点数的取值范围是 [1, 100]
 * 0 <= Node.val <= 1000
 * 思路：
 * 1.在中序遍历的时候，修改节点指向
 * 2.具体地，当我们遍历到一个节点时，把它的左孩子设为空
 * 2.并将其本身作为上一个遍历到的节点的右孩子
 */
public class Num897_IncreaseBST {

    //当前处理到节点的上一个节点
    private TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyHead=new TreeNode(-1);
        cur=dummyHead;
        //在中序遍历中修改节点指向达到修改后的效果
        increasingBSTHelper(root);
        return dummyHead.right;
    }

    /**
     * 把二叉搜索树变为递增的二叉树并且没有左侧节点
     * 分析：中序遍历达到递增，同时将中序遍历得到节点作为上一个处理过的节点的右孩子
     * 节点左孩子置空
     * @param root
     */
    private void increasingBSTHelper(TreeNode root) {
        if(root==null){
            return;
        }
        increasingBSTHelper(root.left);
        cur.right=root;
        root.left=null;
        cur=root;
        increasingBSTHelper(root.right);
    }
}
